/*
*   树状数组应用
*/


//307.区域和检索-数组可修改
//https://leetcode.cn/problems/range-sum-query-mutable/
class NumArray {
    vector<int> tree; //树状数组前缀和
    vector<int> arr;  //原数组

    int NumsSum(int i)
    {
        int ret = 0;
        int n = tree.size();
        //计算当前关键区间和前面的关键区间之和即可得到 (1,index+1) 的区间
        for(;i>0;i-=(i&-i)) ret += tree[i];
        return ret;
    }
public:
    NumArray(vector<int>& nums):arr(nums),tree(nums.size()+1)
    {
        int n = tree.size();
        //将数组更新到树状数组和原数组

        //O(nlogn)处理方法
        //for(int i = 0;i<n;++i) update(i,nums[i]);

        //O(n)处理方法
        for(int i = 1;i<n;++i)
        {
            tree[i] += nums[i-1];
            int next = i+(i&-i); //计算下一个关键区间
            if(next < n) tree[next] += tree[i]; //将当前值的变化加入下一个关键区间
            //这样 当前关键区间的变化就会影响后面包含自己关键区间的前缀和
            //一趟遍历即可更新所有数组前缀和
        }
    }
    
    // (i&-i) 得到 i 的最低位二进制比特位
    void update(int index, int val) {
        int diff = val-arr[index];
        arr[index] = val; //更新arr的值
        int n = tree.size();
        //更新当前状态数 更新后面包含该关键区间的数组
        for(int i = index+1;i<n;i+=(i&-i)) tree[i] += diff;
    }
    
    int sumRange(int left, int right) {
        //右边区间+1的前缀和[1,right+1] 减去 左区间前面的值[1,left] 就是 区间值
        return NumsSum(right+1)-NumsSum(left);
    }
};


//3072.将元素分配到两个数组中II
//https://leetcode.cn/problems/distribute-elements-into-two-arrays-ii/
class TreeArray
{
    vector<int> tree;
public:
    TreeArray(int n):tree(n+1) {}

    //将i位置的数字加1
    void update(int i)
    {
        int n = tree.size();
        while(i<n)
        {
            ++tree[i];
            i += (i&-i);
        }
    }

    //获取[0,i]的数字之和
    int presum(int i)
    {
        int n = tree.size();
        int ret = 0;
        while(i>0)
        {
            ret += tree[i];
            i -= (i&-i);
        }
        return ret;
    }


};
class Solution {
    void UniqueArr(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        unique(nums.begin(),nums.end());
        unordered_map<int,int> hash;
        for(int n:nums) ++hash[n];
        nums.resize(hash.size());
    }
public:
    vector<int> resultArray(vector<int>& nums) {
        vector<int> arr(nums);
        UniqueArr(arr);
        unordered_map<int,int> hash;
        int m = nums.size(),n = arr.size();
        //将去重后的数字下标与其映射 要+1 因为树状数组需要从1开始 否则死循环
        for(int i = 0;i<n;++i) hash[arr[i]]=i+1;

        //记录每个数字出现的次数 因为可能重复出现 所以使用去重数组后的下标作为记录
        TreeArray ta1(n),ta2(n);
        vector<int> arr1{nums[0]},arr2{nums[1]};
        ta1.update(hash[nums[0]]); ta2.update(hash[nums[1]]);

        //开始分配数组
        for(int i = 2;i<m;++i)
        {
            int val = nums[i];
            int idx = hash[nums[i]];

            int a1 = arr1.size(),a2 = arr2.size();
            //计算有多少元素大于当前元素
            int sum1 = a1-ta1.presum(idx),sum2 = a2-ta2.presum(idx);
            if(sum1>sum2 ||(sum1==sum2 && a1<=a2))
            {
                arr1.push_back(val);
                ta1.update(idx);
            }
            else
            {
                arr2.push_back(val);
                ta2.update(idx);
            }
        }
        arr1.reserve(nums.size());
        for(int num:arr2) arr1.push_back(num);
        return arr1;
    }
};


